package main

import (
	"fmt"
)

const SIZE = 9

func printBoard(board [SIZE][SIZE]int) {
	for r := 0; r < SIZE; r++ {
		for c := 0; c < SIZE; c++ {
			val := board[r][c]
			if val == 0 {
				fmt.Print(". ")
			} else {
				fmt.Printf("%d ", val)
			}
		}
		fmt.Println()
	}
}

func isValid(board [SIZE][SIZE]int, row, col, num int) bool {
	// Check row
	for c := 0; c < SIZE; c++ {
		if board[row][c] == num {
			return false
		}
	}
	// Check column
	for r := 0; r < SIZE; r++ {
		if board[r][col] == num {
			return false
		}
	}
	// Check 3x3 box
	boxRowStart := (row / 3) * 3
	boxColStart := (col / 3) * 3
	for r := boxRowStart; r < boxRowStart+3; r++ {
		for c := boxColStart; c < boxColStart+3; c++ {
			if board[r][c] == num {
				return false
			}
		}
	}
	return true
}

func findEmptyCell(board [SIZE][SIZE]int) (int, int, bool) {
	for r := 0; r < SIZE; r++ {
		for c := 0; c < SIZE; c++ {
			if board[r][c] == 0 {
				return r, c, true
			}
		}
	}
	return 0, 0, false
}

func solveSudoku(board *[SIZE][SIZE]int) bool {
	row, col, found := findEmptyCell(*board)
	if !found {
		return true // solved
	}

	for num := 1; num <= 9; num++ {
		if isValid(*board, row, col, num) {
			board[row][col] = num
			if solveSudoku(board) {
				return true
			}
			board[row][col] = 0 // backtrack
		}
	}
	return false
}

func main() {
	testBoards := [10][SIZE][SIZE]int{
		{ // Example 1
			{5, 3, 0, 0, 7, 0, 0, 0, 0},
			{6, 0, 0, 1, 9, 5, 0, 0, 0},
			{0, 9, 8, 0, 0, 0, 0, 6, 0},
			{8, 0, 0, 0, 6, 0, 0, 0, 3},
			{4, 0, 0, 8, 0, 3, 0, 0, 1},
			{7, 0, 0, 0, 2, 0, 0, 0, 6},
			{0, 6, 0, 0, 0, 0, 2, 8, 0},
			{0, 0, 0, 4, 1, 9, 0, 0, 5},
			{0, 0, 0, 0, 8, 0, 0, 7, 9},
		},
		{ // Example 2
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 3, 0, 8, 5},
			{0, 0, 1, 0, 2, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 7},
			{0, 0, 0, 0, 1, 0, 0, 0, 0},
			{3, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 4, 0, 1, 0, 0},
			{5, 7, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
		{ // Example 3
			{1, 0, 0, 0, 0, 7, 0, 9, 0},
			{0, 3, 0, 0, 2, 0, 0, 0, 8},
			{0, 0, 9, 6, 0, 0, 5, 0, 0},
			{0, 0, 5, 3, 0, 0, 9, 0, 0},
			{0, 1, 0, 0, 0, 0, 0, 0, 2},
			{0, 0, 6, 0, 0, 3, 0, 0, 0},
			{0, 6, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
		{ // Example 4
			{0, 0, 0, 2, 6, 0, 7, 0, 1},
			{6, 8, 0, 0, 7, 0, 0, 9, 0},
			{1, 9, 0, 0, 0, 4, 5, 0, 0},
			{8, 2, 0, 1, 0, 0, 0, 4, 0},
			{0, 0, 4, 6, 0, 2, 9, 0, 0},
			{0, 5, 0, 0, 0, 3, 0, 2, 8},
			{0, 0, 9, 3, 0, 0, 0, 7, 4},
			{0, 4, 0, 0, 5, 0, 0, 3, 6},
			{7, 0, 3, 0, 1, 8, 0, 0, 0},
		},
		{ // Example 5
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 3, 0, 8, 5},
			{0, 0, 1, 0, 2, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 7},
			{0, 0, 0, 0, 1, 0, 0, 0, 0},
			{3, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 4, 0, 1, 0, 0},
			{5, 7, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
		{ // Example 6
			{0, 0, 0, 0, 0, 0, 0, 0, 6},
			{0, 0, 0, 0, 0, 3, 0, 0, 0},
			{0, 0, 1, 0, 2, 0, 0, 0, 0},
			{0, 0, 0, 0, 6, 0, 0, 0, 3},
			{4, 0, 0, 8, 0, 3, 0, 0, 1},
			{7, 0, 0, 0, 2, 0, 0, 0, 6},
			{0, 6, 0, 0, 0, 0, 2, 8, 0},
			{0, 0, 0, 4, 1, 9, 0, 0, 5},
			{0, 0, 0, 0, 8, 0, 0, 7, 9},
		},
		{ // Example 7
			{9, 0, 0, 0, 0, 0, 0, 0, 5},
			{0, 1, 0, 0, 0, 5, 0, 0, 0},
			{0, 0, 0, 3, 0, 0, 0, 8, 0},
			{0, 0, 0, 0, 0, 6, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 2, 0, 0},
			{3, 0, 7, 0, 0, 0, 0, 0, 1},
			{0, 6, 0, 0, 0, 0, 0, 9, 0},
			{0, 0, 0, 4, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
		{ // Example 8
			{2, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 3, 0, 8, 5},
			{0, 0, 1, 0, 2, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 7},
			{0, 0, 0, 0, 1, 0, 0, 0, 0},
			{3, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 4, 0, 1, 0, 0},
			{5, 7, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
		{ // Example 9
			{0, 0, 0, 0, 7, 0, 0, 0, 0},
			{6, 0, 0, 1, 9, 5, 0, 0, 0},
			{0, 9, 8, 0, 0, 0, 0, 6, 0},
			{8, 0, 0, 0, 6, 0, 0, 0, 3},
			{4, 0, 0, 8, 0, 3, 0, 0, 1},
			{7, 0, 0, 0, 2, 0, 0, 0, 6},
			{0, 6, 0, 0, 0, 0, 2, 8, 0},
			{0, 0, 0, 4, 1, 9, 0, 0, 5},
			{0, 0, 0, 0, 8, 0, 0, 7, 0},
		},
		{ // Example 10
			{0, 0, 0, 4, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 3, 0, 8, 5},
			{0, 2, 1, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 7},
			{0, 0, 0, 0, 1, 0, 0, 0, 0},
			{3, 0, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 4, 0, 1, 0, 0},
			{5, 7, 0, 0, 0, 0, 0, 0, 0},
			{0, 0, 0, 0, 0, 0, 0, 0, 0},
		},
	}

	for i := 0; i < 10; i++ {
		fmt.Printf("Test Sudoku #%d (Before):\n", i+1)
		printBoard(testBoards[i])
		if solveSudoku(&testBoards[i]) {
			fmt.Printf("Solved Sudoku #%d:\n", i+1)
			printBoard(testBoards[i])
		} else {
			fmt.Printf("No solution found for Sudoku #%d.\n", i+1)
		}
		fmt.Println("-----------------------------------------")
	}
}
